Test 2019.8.14 题解

2019-08-14

题目传送门

T1 T2 T3 T4 T5

题解

T1 NBA 总冠军

一看题面，哎哎哟，不是一道超级水题吗，啪啪啪，飞速的打完代码，一过样例，直接提交。

但是，但是，这这这 ~~作为一个观看NBA10几年的老粉~~。居然没有想到洛杉矶湖人（Los angels）。

好吧，这看似简单的题面难度瞬间上了一个档次：

1.geline 读入

2.分出名字和时间

3.去掉c里的时间

4.结构体排序

5.边去重边输出

#include<bits/stdc++.h>
#define re register int
using namespace std;
struct NBA{string c;int t;}a[51];
int n,x;
bool cmp(NBA x,NBA y){return x.t<y.t;}
int main(){
    scanf("%d\n",&n);
    for(int i=1;i<=n;++i){
        getline(cin,a[i].c);
        x=0;
        for(int j=0;j<a[i].c.length();++j)
            if((a[i].c[j]>='0')&&(a[i].c[j]<='9'))x=x*10+a[i].c[j]-'0';   //查找时间
        a[i].t=x;a[i].c.erase(a[i].c.size()-5,5);   //去掉字符串的时间
    }
    sort(a+1,a+n+1,cmp);   //结构体排序
    for(int i=1;i<=n;++i)
        if(a[i].t!=a[i-1].t)   //去重
            cout<<a[i].t<<" "<<a[i].c<<endl;    //输出
    return 0;
}

ps:因为 ~~本blog猪~~ 的代码仍未调试正确，本代码来自:https://www.luogu.org/blog/gzhqyx/nba-zong-guan-jun

~~blog猪~~ 的代码本地CCR是正确的，在 Linux 的评测机上却错了，据说是因为回车上的玄学问题……

T2 骑马修栅栏

吃了没文化的亏，一直以为是连通块的问题，打了个暴搜，最后老师讲评才知道是一道欧拉环的问题。判断每个点的入度是不是都为偶数，如果是输出”Can be achieve”,否则记录点，输出”Can not be achieve”.

#include<bits/stdc++.h>
#define re register int
using namespace std;
int s[539],n,a,b,x[4],y=1;
int main(){
    scanf("%d",&n);
    for(re i=1;i<=n;i++){
        scanf("%d%d",&a,&b);s[a]++,s[b]++;   //记录入度
    }
    for(re i=1;i<=530;i++){
        if(s[i]%2)x[y++]=i;   //如果入度为奇数，则记录
    }
    if(x[1]){     //如果x[1]被记录过
        printf("Can not be achieve\n");   //输出
        printf("%d %d",x[1],x[2]);    //输出
    }
    else printf("Can be achieve");
    return 0;
}

T3 传话

一道图论题,我考试的时候打了个假的图论(邻接矩阵)，n4的复杂度……思路很乱。正解的话应该是用邻接表，枚举时仅用n的复杂度就行，搜索的话看优化，最多可以到m的复杂度，所以最后复杂度是O(nm)

T4 硬币

一道完全背包+拆分。因为考虑到数字的浮动性，所以我们可以把硬币的重量拆分出来，例:5 40 41可拆分成5 40和5 41;

-------------本文结束感谢您的阅读-------------

本文作者： jfy
本文链接： http://example.com/2019/08/14/Test%202019.8.14/
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！